package com.qch.edu.lagou.sort;

import java.util.Arrays;

/**
 * @Author qch
 * @Date 2021/7/21
 * 4.堆排序：O(nlog^n)
 *
 * 因为是完全二叉树所以节点对应的位置都能以数组存储并塞满
 * 左孩子地址 2i+1
 * 右孩子地址 2i+2
 * 第一个非叶子节点地址 （2i+1=arr.length-1）=》arr.length/2-1
 * 思路
 * ：1.将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
 *   2.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
 *   3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
 */
public class HeapSort {

    public static void sort(int[] arr) {
        //1.把无序数组构建成一个大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        /**    8
         * 7        4
         *5   6    2  3
         *
         */
        //2.调整堆结构，堆顶与末尾元素交换，产生新堆，再调整
        //最后一个：arr[i],最大arr[0]

        for (int i = arr.length - 1; i > 0; i--) {
                int tmp=arr[i];
                arr[i]=arr[0];
                arr[0]=tmp;
                //调整大顶堆
            adjustHeap(arr,0,i);
        }
        /**
         *    2
         *  3    4
         * 5 6  7 8
         *
         */
    }

    /**
     * 第一个非叶子节点 arr.length/2- 1，从左至右，从上至下
     * @param arr
     * @param parent
     * @param len
     */
    public static void adjustHeap(int[] arr, int parent, int len) {
        //创建一个临时变量用来保存父节点的值
        int tmp = arr[parent];
        //左孩子
        int child = 2 * parent + 1;
        while (child < len) {
            //child+1代表右孩子位置；右孩子大于左孩子
            if (child + 1 < len && arr[child + 1] > arr[child]) {
                //右孩子
                child++;
            }
            //child可能是左或是右
            if (tmp >= arr[child]) {
                //不用交换
                break;
            }
            //交换
            arr[parent] = arr[child];
            // arr[child]=tmp;
            //child指针移动(想不出来，好好看看)
            //把子位置给父位置
            parent = child;

            //此时的parent相当于child
            arr[parent] = tmp;
            //找下一个子位置
            child = child * 2 + 1;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 7, 3, 5, 6, 2, 8};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
